package com.hdu.other.monotonyQueue;

public class lc862 {
    class Solution {
        public int shortestSubarray(int[] nums, int k) {
            int len = nums.length;
            long[] preSum = new long[len + 1];
            for (int i = 0; i < len; i++) {
                preSum[i + 1] = preSum[i] + nums[i];
            }
            int[] q = new int[len + 1];
            int h = 0, t = 0;
            int ans = Integer.MAX_VALUE;
            for (int i = 0; i <= len; i++) {
                while (h < t && preSum[i] - preSum[q[h]] >= k) {
                    ans = Math.min(ans, i - q[h++]);
                }
                while (h < t && preSum[q[t - 1]] >= preSum[i]) {
                    t--;
                }
                q[t++] = i;
            }
            return ans < Integer.MAX_VALUE ? ans : -1;
        }
    }
}
